class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) { return head; }
        ListNode* slow = head;//慢指针
        ListNode* fast = head;//快指针
        ListNode* precious = head;
        while (fast && fast->next) {
            precious = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        precious->next = NULL;//断开
        return merge(sortList(head), sortList(slow));
    }
    // 或者可以这样写，无precious版本
    //ListNode* sortList(ListNode* head) {
    //    if (!head || !head->next) { return head; }
    //    ListNode* slow = head;//慢指针
    //    ListNode* fast = head->next;//快指针
    //    while (fast && fast->next) {
    //        slow = slow->next;
    //        fast = fast->next->next;
    //    }
    //    ListNode* right = slow->next;
    //    slow->next = NULL;
    //    return merge(sortList(head), sortList(right));
    //}
    ListNode* merge(ListNode* list1, ListNode* list2) {// 合并两个链表模板
        if (list1 == NULL) {
            return list2;
        }
        if (list2 == NULL) {
            return list1;
        }

        if (list1->val < list2->val) {
            list1->next = merge(list1->next, list2);
            return list1;
        }
        else {
            list2->next = merge(list1, list2->next);
            return list2;
        }
    }

};